#ifndef TWENTY_FOUR_H
#define TWENTY_FOUR_H

enum Color {
    White,
    Gray,
    Black,
};

struct TF_Item {
    int v;
    int d;
    int f;
    int e;
    int heap_i;
    enum Color color;
    struct TF_Node * dfs_pi;
    struct TF_Node * pi;
    struct TF_Adjacency_List * list;
    int h;
};

struct TF_Node {
    struct TF_Item v;
    struct TF_Node * pre;
    struct TF_Node * next;
};

struct TF_List {
    struct TF_Node * head;
    struct TF_Node * tail;
    int count;
};

struct TF_Adjacency_Item {
    struct TF_Node * v;
    int w;
};

struct TF_Adjacency_Node {
    struct TF_Adjacency_Item v;
    struct TF_Adjacency_Node * next;
};

struct TF_Adjacency_List {
    struct TF_Adjacency_Node * head;
    struct TF_Adjacency_Node * tail;
    int count;
};

void TF_list_insert(struct TF_List * list, int v);
int TF_list_is_empty(struct TF_List * list);
struct TF_Node * TF_list_find(struct TF_List * list, int v);
void TF_list_clear(struct TF_List * list);
void TF_node_show(struct TF_Node * node);
void TF_list_show(struct TF_List * list);

int TF_adjacency_list_is_empty(struct TF_Adjacency_List * list);
void TF_adjacency_list_insert(struct TF_Adjacency_List * list, struct TF_Node * node, int w);
void TF_adjacency_list_clear(struct TF_Adjacency_List * list);
void TF_adjacency_node_show(struct TF_Adjacency_Node * node);
void TF_adjacency_list_show(struct TF_Adjacency_List * list);

void relax(struct TF_Node * u, struct TF_Node * v, int w);
void pi_show(struct TF_List * list);

// 解决一般情况下的单源最短路径问题
// 边的权重可以为负值
// 返回值用于表明是否存在一个从源节点可以到达的权重为负值的环路
int bellman_ford(struct TF_List * list, struct TF_Node * s);

// 解决有向无环图中的单源最短路径问题
void dfs(struct TF_List * list);
void dfs_visit(struct TF_Node * node, int * time);
void topological_sort(struct TF_List * list);
struct TF_Node * find_max_e(struct TF_Node * node);

void dag_shortest_paths(struct TF_List * list);

struct TF_HEAP {
    struct TF_Node ** list;
    int size;
};

void min_heapify(struct TF_HEAP * q, int i);
void build_min_heap(struct TF_HEAP * q);
void heapsort(struct TF_HEAP * q);
void heap_insert(struct TF_HEAP * q, struct TF_Node * node);
struct TF_Node * minmum(struct TF_HEAP * q);
void heap_decrease_key(struct TF_HEAP * q, int i, int k);
struct TF_Node * heap_extract_min(struct TF_HEAP * q);

void dijkstra(struct TF_List * list);

#endif // TWENTY_FOUR_H

/*
    struct TF_List list = {NULL, NULL, 0};
    TF_list_insert(&list, 1);
    TF_list_insert(&list, 2);
    TF_list_insert(&list, 3);
    TF_list_insert(&list, 4);
    TF_list_insert(&list, 5);

    struct TF_Node * current = list.head;

    struct TF_Adjacency_List ad_list_1 = {NULL, NULL, 0};
    TF_adjacency_list_insert(&ad_list_1, TF_list_find(&list, 2), 10);
    TF_adjacency_list_insert(&ad_list_1, TF_list_find(&list, 5), 5);
    current->v.list = &ad_list_1;
    current = current->next;

    struct TF_Adjacency_List ad_list_2 = {NULL, NULL, 0};
    TF_adjacency_list_insert(&ad_list_2, TF_list_find(&list, 3), 1);
    TF_adjacency_list_insert(&ad_list_2, TF_list_find(&list, 4), 2);
    current->v.list = &ad_list_2;
    current = current->next;

    struct TF_Adjacency_List ad_list_3 = {NULL, NULL, 0};
    TF_adjacency_list_insert(&ad_list_3, TF_list_find(&list, 4), 4);
    current->v.list = &ad_list_3;
    current = current->next;

    struct TF_Adjacency_List ad_list_4 = {NULL, NULL, 0};
    TF_adjacency_list_insert(&ad_list_4, TF_list_find(&list, 1), 7);
    TF_adjacency_list_insert(&ad_list_4, TF_list_find(&list, 3), 6);
    current->v.list = &ad_list_4;
    current = current->next;

    struct TF_Adjacency_List ad_list_5 = {NULL, NULL, 0};
    TF_adjacency_list_insert(&ad_list_5, TF_list_find(&list, 2), 3);
    TF_adjacency_list_insert(&ad_list_5, TF_list_find(&list, 3), 9);
    TF_adjacency_list_insert(&ad_list_5, TF_list_find(&list, 4), 2);
    current->v.list = &ad_list_5;
    TF_list_show(&list);

//    bellman_ford(&list, TF_list_find(&list, 1));
//    printf("---------------\n");
//    TF_list_show(&list);
//    printf("---------------\n");
//    pi_show(&list);

//    printf("---------------\n");
//    topological_sort(&list);
//    TF_list_show(&list);

//    printf("---------------\n");
//    dag_shortest_paths(&list);
//    TF_list_show(&list);
//    printf("---------------\n");
//    pi_show(&list);

    dijkstra(&list);
    TF_list_show(&list);
    pi_show(&list);

    TF_list_clear(&list);
 */
